Enterprise networks are increasingly moving from using dedicated private lines to using virtual private networks (VPNs) and, more particularly, using network layer Multi-Protocol Label Switching (MPLS) to connect geographically disparate sites. In an MPLS network architecture, each network site has one or more customer edge routers (CERs), which may be jointly configured by the customer and/or a service provider that provides network service between the CERs. Each CER connects to one or more provider edge routers (PERs) in the network. Internet protocol (IP) traffic from a CER that originates from or is destined for the customer is encapsulated by MPLS labels at the ingress PER, carried over MPLS tunnels across routers in an MPLS backbone network, decapsulated by a remote PER, and sent to the appropriate destination CER. Such provider-based VPNs provide a scalable and secure way for a service provider to support VPN services for many different customers using a common MPLS backbone network.